package _interview75;

import java.util.HashSet;
import java.util.Set;

/**
 * 547. 省份数量
 */
public class No547 {
    private int ans;
    private Set<Integer> path;
    private int[][] isConnected;

    public int findCircleNum(int[][] isConnected) {
        path = new HashSet<>();
        this.isConnected = isConnected;
        int n = isConnected.length;

        for (int i = 0; i < n; i++) {
            path.add(i);
        }
        while (!path.isEmpty()) {
            dfs(path.iterator().next());
            ans++;
        }

        return ans;
    }

    private void dfs(int i) {
        path.remove(i);
        for (int j = 0; j < isConnected[i].length; j++) {
            if (isConnected[i][j] == 1 && path.contains(j)) dfs(j);
        }
    }
}
